package mazeAssignment.solve;

import mazeAssignment.*;
import java.util.ArrayDeque;

/**
 * Implements the RightHandSolve maze solving algorithm utilizing a stack (ArrayDeque).
 * @author Marcel Hekman
 */
public class RightHandSolveStack implements Solve
{
	private static final int NORTH = 0;
	private static final int EAST = 1;
	private static final int SOUTH = 2;
	private static final int WEST = 3;
	
	protected Maze maze;
	private boolean finished;
	private int direction;
	private int posX;
	private int posY;
	private int sizeX;
	private int sizeY;
	
	private ArrayDeque<Integer> backtrackStack;
	private ArrayDeque<Integer> directionStack;
	
	
	@Override
	public void initialise(Maze m) throws SolveException
	{
		this.maze = m;
		this.sizeX = m.getSizeX();
		this.sizeY = m.getSizeY();
		this.finished = false;
		this.backtrackStack = new ArrayDeque<Integer>((sizeX + sizeY) * 2);
		this.directionStack = new ArrayDeque<Integer>((sizeX + sizeY) * 2);
		
		findStart();
	}

	@Override
	public boolean isDone()
	{
		return finished;
	}

	@Override
	public void tick() throws SolveException
	{
		if(finished)
			throw new SolveException("tick(): Already finished.");
		
		boolean forward = tryForward();
		
		if(forward)
		{
			if(maze.getSolveState(posX, posY) == Maze.SOLVE_END)
			{
				this.finished = true;
			}
		}
		else
		{
			goBackward();
		}
	}
	
	private boolean tryForward()
	{
		backtrackStack.push( posX + (posY * sizeX) );
		directionStack.push( direction );
		
		turnRight();
		if(tryDirection())
			return true;
		
		turnLeft();
		if(tryDirection())
			return true;
		
		turnLeft();
		if(tryDirection())
			return true;
		
		backtrackStack.pop();
		directionStack.pop();
		
		return false;
	}
	
	private boolean tryDirection()
	{
		//North
		if(direction == NORTH && posY > 0 && ! maze.getNorth(posX, posY) &&
				! maze.isVisited(posX, posY-1))
		{
			maze.visit(posX, posY-1);
			posY--;
			return true;
		}
		
		//East
		else if(direction == EAST && (posX+1) < sizeX && ! maze.getEast(posX, posY) &&
				! maze.isVisited(posX+1, posY))
		{
			maze.visit(posX+1, posY);
			posX++;
			return true;
		}
		
		//South
		else if(direction == SOUTH && (posY+1) < sizeY && ! maze.getSouth(posX, posY) &&
				! maze.isVisited(posX, posY+1))
		{
			maze.visit(posX, posY+1);
			posY++;
			return true;
		}
		
		//West
		else if(direction == WEST && posX > 0 && ! maze.getWest(posX, posY) &&
				! maze.isVisited(posX-1, posY))
		{
			maze.visit(posX-1, posY);
			posX--;
			return true;
		}
		
		return false;
	}
	
	private void goBackward()
	{
		maze.markAsInvalid(posX, posY);
		
		int previous = backtrackStack.pop();
		
		this.posX = previous % sizeX;
		this.posY = previous / sizeX;
		this.direction = directionStack.pop();
	}
	
	private void turnLeft()
	{
		direction = (direction + 3) % 4;
	}
	
	private void turnRight()
	{
		direction = (direction + 1) % 4;
	}
	
	/**
	 * Finds the start item in the maze
	 * Assumes the start point is not in the center of the maze.
	 * @throws SolveException If no start element is found.
	 */
	private void findStart() throws SolveException
	{
		//Search the entire maze
		for(int x = 0; x < sizeX; x++)
		{
			for(int y = 0; y < sizeY; y++)
			{
				if(maze.getSolveState(x, y) == Maze.SOLVE_START)
				{
					this.posX = x;
					this.posY = y;
					
					if(!maze.getNorth(x, y))
						direction = NORTH;

					else if(!maze.getEast(x, y))
						direction = EAST;

					else if(!maze.getSouth(x, y))
						direction = SOUTH;

					else if(!maze.getWest(x, y))
						direction = WEST;
					return;
				}
			}
		}
		
		throw new SolveException("findStart: Unable to find start element.");
	}
}
